package edu.cuit.avatar.parallel;

import java.util.Arrays;
import java.util.Random;

/**
 * 归并排序：
 *  归并排序将数组分为两半，对每部分递归地应用归并排序，在两部分都排好序后，对它们进行合并。
 *      递归调用持续将数组划分为子数组，直到每个子数组只包含一个元素。
 *      然后，该算法将这些小的子数组归并为稍大的子数组，直到最后形成一个有序的数组。
 * @author <a href="mailto:1020zhaodan@163.com">Adan</a>
 * @version 1.0
 * @date 2025/7/18 8:56
 */
public class MergeSort {
    public static void sort(int[] list){
        if(list.length > 1){ //递归终止条件:每个子数组只包含一个元素
            //将数组拆分为两半(第一部分)
            int[] firstHalf = new int[list.length / 2];
            System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
            //在第一部分递归调用归并排序
            sort(firstHalf);

            //将数组拆分为两半(第二部分)
            int size = list.length - list.length / 2;
            int[] secondHalf = new int[size];
            System.arraycopy(list, list.length / 2, secondHalf, 0, size);
            //在第二部分递归调用归并排序
            sort(secondHalf);

            //在firstHalf, secondHalf都排好序后，将它们归并成一个新的有序数组list
            merge(firstHalf, secondHalf, list);
        }
    }

    /**
     * 归并两个有序数组为临时数组temp
     * @param list1 有序数组1
     * @param list2 有序数组2
     * @param temp 归并为稍大的子数组(有序)
     */
    public static void merge(int[] list1, int[] list2, int[] temp){
        int index1 = 0,
            index2 = 0,
            index3 = 0;

        while(index1 < list1.length && index2 < list2.length){
            if(list1[index1] < list2[index2]){
                temp[index3++] = list1[index1++];
            } else {
                temp[index3++] = list2[index2++];
            }
        }
        //处理各自数组中剩余的元素
        while(index1 < list1.length){ //如果list1中仍有未拷贝的元素
            temp[index3++] = list1[index1++];
        }

        //处理各自数组中剩余的元素
        while(index2 < list2.length){ //如果list2中仍有未拷贝的元素
            temp[index3++] = list2[index2++];
        }
    }

    public static void main(String[] args) {
        int[] list = new int[10];
        var random = new Random();
        for(var i = 0; i < list.length; i++)
            list[i] = random.nextInt(100);

        System.out.println("排序前:" + Arrays.toString(list));
        sort(list);
        System.out.println("排序后:" + Arrays.toString(list));
    }
}
